{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Nodes Equal to Average of Subtree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: averageOfSubtree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计值等于子树平均值的节点数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉树的根节点 <code>root</code> ，找出并返回满足要求的节点数，要求节点的值等于其 <strong>子树</strong> 中值的 <strong>平均值</strong> 。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n</code> 个元素的平均值可以由 <code>n</code> 个元素 <strong>求和</strong> 然后再除以 <code>n</code> ，并 <strong>向下舍入</strong> 到最近的整数。</li>\n",
    "\t<li><code>root</code> 的 <strong>子树</strong> 由 <code>root</code> 和它的所有后代组成。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/03/15/image-20220315203925-1.png\" style=\"width: 300px; height: 212px;\">\n",
    "<pre><strong>输入：</strong>root = [4,8,5,0,1,null,6]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>\n",
    "对值为 4 的节点：子树的平均值 (4 + 8 + 5 + 0 + 1 + 6) / 6 = 24 / 6 = 4 。\n",
    "对值为 5 的节点：子树的平均值 (5 + 6) / 2 = 11 / 2 = 5 。\n",
    "对值为 0 的节点：子树的平均值 0 / 1 = 0 。\n",
    "对值为 1 的节点：子树的平均值 1 / 1 = 1 。\n",
    "对值为 6 的节点：子树的平均值 6 / 1 = 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/03/26/image-20220326133920-1.png\" style=\"width: 80px; height: 76px;\">\n",
    "<pre><strong>输入：</strong>root = [1]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>对值为 1 的节点：子树的平均值 1 / 1 = 1。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目在范围 <code>[1, 1000]</code> 内</li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-nodes-equal-to-average-of-subtree](https://leetcode.cn/problems/count-nodes-equal-to-average-of-subtree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-nodes-equal-to-average-of-subtree](https://leetcode.cn/problems/count-nodes-equal-to-average-of-subtree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,8,5,0,1,null,6]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(root):\n",
    "            nonlocal ans\n",
    "            if root is None:\n",
    "                return 0, 0\n",
    "            \n",
    "            sum_left, count_left = dfs(root.left)\n",
    "            sum_right, count_right = dfs(root.right)\n",
    "            sum_current = root.val + sum_left + sum_right\n",
    "            count_current = 1+count_left+count_right\n",
    "            if sum_current//count_current == root.val:\n",
    "                ans+=1\n",
    "            return sum_current, count_current\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def bianli(node):\n",
    "            li = [node]\n",
    "            ssum = 0\n",
    "            gs = 0\n",
    "            while li:\n",
    "                now_node = li.pop(0)\n",
    "                ssum += now_node.val\n",
    "                gs += 1\n",
    "                if now_node.left:\n",
    "                    li.append(now_node.left)\n",
    "              \n",
    "                if now_node.right:\n",
    "                    li.append(now_node.right)\n",
    "              \n",
    "\n",
    "            return ssum,gs\n",
    "\n",
    "        count = 0\n",
    "        sli = [root]\n",
    "        while sli:\n",
    "            nn = sli.pop(0)\n",
    "            s,g = bianli(nn)\n",
    "            # return s,g\n",
    "            if s//g == nn.val:\n",
    "                count += 1\n",
    "            if nn.left:\n",
    "                sli.append(nn.left)\n",
    "            if nn.right:\n",
    "                sli.append(nn.right)\n",
    "        return count\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        self.answer = 0\n",
    "\n",
    "    def postorder(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root == None:\n",
    "            return [0, 0]\n",
    "\n",
    "        leftSum, leftNode = self.postorder(root.left)\n",
    "        rightSum, rightNode = self.postorder(root.right)\n",
    "\n",
    "        subtreeSum = leftSum + rightSum + root.val\n",
    "        subtreeNode = leftNode + rightNode + 1\n",
    "        if root.val == subtreeSum // subtreeNode:\n",
    "            self.answer += 1\n",
    "\n",
    "        return [subtreeSum, subtreeNode]\n",
    "\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        retVal = 0\n",
    "\n",
    "        if root == None:\n",
    "            return retVal\n",
    "\n",
    "        self.answer = 0\n",
    "        self.postorder(root)\n",
    "        retVal = self.answer\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        # 相当于先序遍历了 \n",
    "        def dfs(root: Optional[TreeNode]):\n",
    "            nonlocal ans \n",
    "            if not root:\n",
    "                return 0, 0\n",
    "            \n",
    "            l = dfs(root.left)\n",
    "            r = dfs(root.right)\n",
    "            # value左右子树之和，count左右子树节点总和\n",
    "            value = l[0] + r[0] + root.val\n",
    "            count = l[1] + r[1] + 1\n",
    "            if root.val == value // count:\n",
    "                ans += 1\n",
    "            return value, count    \n",
    "        \n",
    "        # 主函数\n",
    "        ans = 0\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "   def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "       ans=0\n",
    "       def dfs(node) :\n",
    "           if node is None : \n",
    "               return 0,0\n",
    "           sum = 0 \n",
    "           cnt= 0\n",
    "           nonlocal ans\n",
    "           leftsum ,leftcnt = dfs(node.left)\n",
    "           sum += node.val + leftsum\n",
    "           cnt +=leftcnt + 1\n",
    "           rightsum, rightcnt = dfs(node.right)\n",
    "           sum += node.val + rightsum\n",
    "           cnt +=rightcnt + 1\n",
    "           if node.val == sum // cnt:ans+=1\n",
    "           return sum,cnt\n",
    "       dfs(root)\n",
    "       return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        # 相当于先序遍历了 \n",
    "        def dfs(root: Optional[TreeNode]):\n",
    "            nonlocal ans \n",
    "            if not root:\n",
    "                return 0, 0\n",
    "            \n",
    "            l = dfs(root.left)\n",
    "            r = dfs(root.right)\n",
    "            # value左右子树之和，count左右子树节点总和\n",
    "            value = l[0] + r[0] + root.val\n",
    "            count = l[1] + r[1] + 1\n",
    "            if root.val == value // count:\n",
    "                ans += 1\n",
    "            return value, count    \n",
    "        \n",
    "        # 主函数\n",
    "        ans = 0\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0, 0\n",
    "            l_val, l_cnt = dfs(root.left)\n",
    "            r_val, r_cnt = dfs(root.right)\n",
    "            tot_val = l_val + r_val + root.val\n",
    "            tot_cnt = l_cnt + r_cnt + 1\n",
    "            if tot_val // tot_cnt == root.val:\n",
    "                nonlocal ans\n",
    "                ans += 1\n",
    "            return tot_val, tot_cnt\n",
    "\n",
    "        ans = 0\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(root):\n",
    "            nonlocal ans\n",
    "            if not root:\n",
    "                return 0, 0 # sum, cnt\n",
    "            ls, lc = dfs(root.left)\n",
    "            rs, rc = dfs(root.right)\n",
    "            s = ls + rs + root.val\n",
    "            c = lc + rc + 1\n",
    "            if s // c == root.val:\n",
    "                ans += 1\n",
    "            return s, c\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "            \n",
    "            # if cur_sum + root.val //\n",
    "\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def search(root):\n",
    "            if not root.left and not root.right:\n",
    "                return root.val, 1, 1\n",
    "            \n",
    "            cur_sum = root.val\n",
    "            cur_node = 1\n",
    "\n",
    "            if root.left:\n",
    "                left_sum, left_node, left_valid_node = search(root.left)\n",
    "                cur_sum += left_sum\n",
    "                cur_node += left_node\n",
    "                # valid_node += left_valid_node\n",
    "                # print(left_valid_node)\n",
    "            \n",
    "            if root.right:\n",
    "                right_sum, right_node, right_valid_node = search(root.right)\n",
    "                cur_sum += right_sum\n",
    "                cur_node += right_node\n",
    "                # valid_node += right_valid_node\n",
    "                # print(right_valid_node)\n",
    "            \n",
    "            valid_node = 0\n",
    "            # if root.val == 4: print(cur_node, cur_sum, left_node, right_node)\n",
    "            if cur_sum // cur_node == root.val:\n",
    "                valid_node += 1\n",
    "                # print(root.val)\n",
    "            if root.left:\n",
    "                valid_node += left_valid_node\n",
    "            if root.right:\n",
    "                valid_node += right_valid_node\n",
    "            \n",
    "            # print(root.val, valid_node)\n",
    "            return cur_sum, cur_node, valid_node\n",
    "        result = search(root)\n",
    "        return result[2]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "       ans=0\n",
    "       def dfs(node) :\n",
    "           if node is None : \n",
    "               return 0,0\n",
    "           sum = 0 \n",
    "           cnt= 0\n",
    "           nonlocal ans\n",
    "           leftsum ,leftcnt = dfs(node.left)\n",
    "           sum += node.val + leftsum\n",
    "           cnt +=leftcnt + 1\n",
    "           rightsum, rightcnt = dfs(node.right)\n",
    "           sum += node.val + rightsum\n",
    "           cnt +=rightcnt + 1\n",
    "           if node.val == sum // cnt:ans+=1\n",
    "           return sum,cnt\n",
    "       dfs(root)\n",
    "       return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        def dfs(root: Optional[TreeNode]):\n",
    "            nonlocal ans\n",
    "            if not root:\n",
    "                return 0, 0\n",
    "            \n",
    "            l = dfs(root.left)\n",
    "            r = dfs(root.right)\n",
    "\n",
    "            value = l[0] + r[0] +root.val\n",
    "            count = l[1] + r[1] + 1\n",
    "\n",
    "            if root.val == value//count:\n",
    "                ans += 1\n",
    "\n",
    "            return value, count\n",
    "\n",
    "        ans = 0\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = 0\n",
    "\n",
    "        def dfs(node: Optional[TreeNode]) -> Tuple[int, int]:\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "            \n",
    "            left, left_num = dfs(node.left)\n",
    "            right, right_num = dfs(node.right)\n",
    "\n",
    "            cur_sum = node.val + left + right\n",
    "            cur_num = left_num + right_num + 1\n",
    "\n",
    "            if cur_sum // cur_num == node.val:\n",
    "                self.ans += 1\n",
    "            \n",
    "            return cur_sum, cur_num\n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "def postprev(node):\n",
    "    if node is None:\n",
    "        return 0, 0, 0\n",
    "    lnum, lsum, lres = postprev(node.left)\n",
    "    rnum, rsum, rres = postprev(node.right)\n",
    "    nums = lnum + rnum + 1\n",
    "    sums = lsum + rsum + node.val\n",
    "    res = lres + rres\n",
    "    if sums // nums == node.val:\n",
    "        res += 1\n",
    "    return nums, sums, res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        _, _, res = postprev(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.cnt = 0\n",
    "        def dfs(node):\n",
    "            if node is None: return 0, 0\n",
    "            n, s = map(sum, zip(dfs(node.left), dfs(node.right), (1, node.val)))\n",
    "            self.cnt += node.val == s // n\n",
    "            return n, s\n",
    "        dfs(root)\n",
    "        return self.cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = [0]\n",
    "\n",
    "        def dfs(node): # [sum,nodes]\n",
    "            if not node:\n",
    "                return [0,0]\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "\n",
    "            summ = left[0]+right[0]+node.val\n",
    "            nodes = left[1]+right[1]+1\n",
    "            if summ//nodes == node.val:\n",
    "                ans[0] += 1\n",
    "            return [summ, nodes]\n",
    "\n",
    "        dfs(root)\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from math import floor\n",
    "\n",
    "class Solution:\n",
    "    ans = 0\n",
    "\n",
    "    def calcNode(self, root: TreeNode) -> (int, int): # count, sum\n",
    "        if root.left is None and root.right is None:\n",
    "            self.ans += 1\n",
    "            return 1, root.val\n",
    "        count = 1\n",
    "        sum = root.val\n",
    "        if root.left is not None:\n",
    "            t = self.calcNode(root.left)\n",
    "            sum += t[1]\n",
    "            count += t[0]\n",
    "        if root.right is not None:\n",
    "            t = self.calcNode(root.right)\n",
    "            sum += t[1]\n",
    "            count += t[0]\n",
    "        if root.val == sum // count:\n",
    "            self.ans += 1\n",
    "        return (count, sum)\n",
    "\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.calcNode(root)\n",
    "        return self.ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root):\n",
    "            nonlocal ans\n",
    "            if not root:\n",
    "                return 0, 0\n",
    "\n",
    "            l = dfs(root.left)\n",
    "            r = dfs(root.right)\n",
    "\n",
    "            value = l[0] + r[0] + root.val\n",
    "            count = l[1] + r[1] + 1\n",
    "            if root.val == (value // count):\n",
    "                ans += 1\n",
    "            return value, count\n",
    "        \n",
    "        ans = 0\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        def bfs(ans,root):\n",
    "            totnum=1\n",
    "            totval=root.val\n",
    "            if root.left:\n",
    "                val,num = bfs(ans,root.left)\n",
    "                totval+=val\n",
    "                totnum+=num\n",
    "            if root.right:\n",
    "                val,num = bfs(ans,root.right)\n",
    "                totval+=val\n",
    "                totnum+=num\n",
    "            if totval//totnum==root.val:\n",
    "                ans[0]+=1\n",
    "            return (totval,totnum)\n",
    "        ans=[0]\n",
    "        bfs(ans,root)\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        # 回溯\n",
    "        def dfs(node):\n",
    "            sm = node.val\n",
    "            cnt = 1\n",
    "            if node.left:\n",
    "                s, c = dfs(node.left)\n",
    "                sm += s\n",
    "                cnt += c\n",
    "            if node.right:\n",
    "                s, c = dfs(node.right)\n",
    "                sm += s\n",
    "                cnt += c\n",
    "            if sm // cnt == node.val:\n",
    "                nonlocal ans\n",
    "                ans += 1\n",
    "            return sm, cnt\n",
    "        dfs(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(rt):\n",
    "            nonlocal ans\n",
    "            tot, count = rt.val, 1\n",
    "            if rt.left:\n",
    "                x, y = dfs(rt.left)\n",
    "                tot += x\n",
    "                count += y\n",
    "            if rt.right:\n",
    "                x, y = dfs(rt.right)\n",
    "                tot += x\n",
    "                count += y\n",
    "            if rt.val == tot // count: ans += 1\n",
    "            return tot, count\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if not root:\n",
    "                return 0, 0\n",
    "            left, cnt1 = dfs(root.left)\n",
    "            right, cnt2 = dfs(root.right)\n",
    "\n",
    "            cur, cur_cnt = left + right + root.val, cnt1 + cnt2 + 1\n",
    "            if root.val == cur // cur_cnt:\n",
    "                res += 1\n",
    "\n",
    "            return cur, cur_cnt\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(now):\n",
    "            res = 0\n",
    "            cnt = 1\n",
    "            s = now.val\n",
    "            if now.left:\n",
    "                left_res, left_cnt, left_s = dfs(now.left)\n",
    "                res += left_res\n",
    "                cnt += left_cnt\n",
    "                s += left_s\n",
    "            \n",
    "            if now.right:\n",
    "                right_res, right_cnt, right_s = dfs(now.right)\n",
    "                res += right_res\n",
    "                cnt += right_cnt\n",
    "                s += right_s\n",
    "            \n",
    "            if s // cnt == now.val:\n",
    "                res += 1\n",
    "            \n",
    "            return res, cnt, s\n",
    "\n",
    "\n",
    "        return dfs(root)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        # 相当于先序遍历了 \n",
    "        def dfs(root: Optional[TreeNode]):\n",
    "            nonlocal ans \n",
    "            if not root:\n",
    "                return 0, 0\n",
    "            \n",
    "            l = dfs(root.left)\n",
    "            r = dfs(root.right)\n",
    "            # value左右子树之和，count左右子树节点总和\n",
    "            value = l[0] + r[0] + root.val\n",
    "            count = l[1] + r[1] + 1\n",
    "            if root.val == value // count:\n",
    "                ans += 1\n",
    "            return value, count    \n",
    "        \n",
    "        # 主函数\n",
    "        ans = 0\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    res = 0\n",
    "\n",
    "    def dfs(self, root: Optional[TreeNode]) -> (int, int):\n",
    "        if root is None:\n",
    "            return 0, 0\n",
    "        \n",
    "        sum = root.val\n",
    "        l_sum, left_size = self.dfs(root.left)\n",
    "        r_sum, right_size = self.dfs(root.right)\n",
    "\n",
    "        sum += l_sum + r_sum\n",
    "        size = left_size+right_size+1\n",
    "        if sum// size == root.val:\n",
    "            self.res += 1\n",
    "        return sum, size\n",
    "\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.dfs(root)\n",
    "\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(node):  #返回sum和node数\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return 0,0  #值是0,增加点数也是0 这样就不影响ans\n",
    "            lv, ln = dfs(node.left)\n",
    "            rv, rn = dfs(node.right)\n",
    "            sm = lv + rv + node.val\n",
    "            nd = ln + rn + 1\n",
    "            if sm // nd == node.val:\n",
    "                ans += 1\n",
    "            return sm, nd\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        # 相当于先序遍历了 \n",
    "        def dfs(root: Optional[TreeNode]):\n",
    "            nonlocal ans \n",
    "            if not root:\n",
    "                return 0, 0\n",
    "            \n",
    "            l = dfs(root.left)\n",
    "            r = dfs(root.right)\n",
    "            # value左右子树之和，count左右子树节点总和\n",
    "            value = l[0] + r[0] + root.val\n",
    "            count = l[1] + r[1] + 1\n",
    "            if root.val == value // count:\n",
    "                ans += 1\n",
    "            return value, count    \n",
    "        \n",
    "        # 主函数\n",
    "        ans = 0\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "   def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "       self.ans=0\n",
    "       def dfs(node) :\n",
    "           if node is None : \n",
    "               return 0,0\n",
    "           sum = 0 \n",
    "           cnt= 0\n",
    "        #    nonlocal ans\n",
    "           leftsum ,leftcnt = dfs(node.left)\n",
    "           sum += node.val + leftsum\n",
    "           cnt +=leftcnt + 1\n",
    "           rightsum, rightcnt = dfs(node.right)\n",
    "           sum += node.val + rightsum\n",
    "           cnt +=rightcnt + 1\n",
    "           if node.val == sum // cnt:self.ans+=1\n",
    "           return sum,cnt\n",
    "       dfs(root)\n",
    "       return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        # 回溯\n",
    "        def dfs(node):\n",
    "            if node == None:\n",
    "                return 0, 0\n",
    "            left_sm, left_cnt = dfs(node.left)\n",
    "            right_sm, right_cnt = dfs(node.right)\n",
    "            sm = left_sm + right_sm + node.val\n",
    "            cnt = left_cnt + right_cnt + 1\n",
    "            if sm // cnt == node.val:\n",
    "                nonlocal ans\n",
    "                ans += 1\n",
    "            return sm, cnt\n",
    "        dfs(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ret = 0\n",
    "        def dfs(root):\n",
    "            nonlocal ret\n",
    "            if not root:\n",
    "                return 0, 0\n",
    "            s1, n1 = dfs(root.left)\n",
    "            s2, n2 = dfs(root.right)\n",
    "            s = s1 + s2 + root.val\n",
    "            n = n1 + n2 + 1\n",
    "            if root.val == s // n:\n",
    "                ret += 1\n",
    "            return s, n\n",
    "        dfs(root)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = 0\n",
    "        self.dfs(root)\n",
    "        return self.ans\n",
    "\n",
    "    def dfs(self, node: TreeNode) -> List[int]:\n",
    "        if not node:\n",
    "            return None\n",
    "\n",
    "        L = self.dfs(node.left)\n",
    "        R = self.dfs(node.right)\n",
    "\n",
    "        vals, count = node.val, 1\n",
    "        if L:\n",
    "            vals += L[0]\n",
    "            count += L[1]\n",
    "        if R:\n",
    "            vals += R[0]\n",
    "            count += R[1]\n",
    "        \n",
    "        per = vals // count\n",
    "        if per == node.val:\n",
    "            self.ans += 1\n",
    "        \n",
    "        return [vals, count]\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if node == None:\n",
    "                return (0,0)\n",
    "\n",
    "            lSum , lCount = dfs(node.left)\n",
    "            rSum , rCount = dfs(node.right)\n",
    "            res = (lSum + rSum + node.val) // (lCount + rCount + 1)\n",
    "\n",
    "            if node.val == res:\n",
    "                ans += 1\n",
    "\n",
    "            return (lSum + rSum + node.val, lCount + rCount + 1)\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        # if not root:\n",
    "        #     return 0\n",
    "        # if not root.right and not root.left:\n",
    "        #     return 1\n",
    "        # def pre_order(root):\n",
    "        #     ans=[]\n",
    "        #     if not root:\n",
    "        #         return 0,0\n",
    "        #     ans=root.val\n",
    "        #     return ans+pre_order(root.left)[0]+pre_order(root.right)[0],1+pre_order(root.left)[1]+pre_order(root.right)[1]\n",
    "        # if pre_order(root)[0]//pre_order(root)[1]==root.val:\n",
    "        #     return 1+self.averageOfSubtree(root.left)+self.averageOfSubtree(root.right)\n",
    "        # return self.averageOfSubtree(root.left)+self.averageOfSubtree(root.right)\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(root):\n",
    "            nonlocal ans\n",
    "            sum_val=0\n",
    "            cnt=0\n",
    "            if not root:\n",
    "                return 0,0\n",
    "            sum_val+=root.val\n",
    "            cnt+=1\n",
    "            if root.left:\n",
    "                s,c=dfs(root.left)\n",
    "                sum_val+=s\n",
    "                cnt+=c\n",
    "            if root.right:\n",
    "                s,c=dfs(root.right)\n",
    "                sum_val+=s\n",
    "                cnt+=c\n",
    "            \n",
    "            if sum_val//cnt==root.val:\n",
    "                ans+=1\n",
    "\n",
    "            return sum_val,cnt\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n",
    "\n",
    "                \n",
    "                \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        def dfs(root: Optional[TreeNode]):\n",
    "            nonlocal ans\n",
    "            if not root:\n",
    "                return 0, 0\n",
    "            \n",
    "            l = dfs(root.left)\n",
    "            r = dfs(root.right)\n",
    "\n",
    "            value = l[0] + r[0] +root.val\n",
    "            count = l[1] + r[1] + 1\n",
    "\n",
    "            if root.val == value//count:\n",
    "                ans += 1\n",
    "\n",
    "            return value, count\n",
    "\n",
    "        ans = 0\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sub_tree_count(self,root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        return 1+self.sub_tree_count(root.left)+self.sub_tree_count(root.right)\n",
    "    def sub_tree_sum(self,root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        return root.val + self.sub_tree_sum(root.left) + self.sub_tree_sum(root.right)\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "    def averageOfSubtree1(self, root: Optional[TreeNode]):\n",
    "        if root is None:\n",
    "            return\n",
    "        if root.val == self.sub_tree_sum(root)//self.sub_tree_count(root):\n",
    "            self.ans+=1\n",
    "            #print(root.val,self.ans)\n",
    "        self.averageOfSubtree1(root.left)\n",
    "        self.averageOfSubtree1(root.right)\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.averageOfSubtree1(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        self.res = 0\n",
    "        def getAverageOfSubtree(node):\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "            left_subtree_sum, left_count = getAverageOfSubtree(node.left)\n",
    "            right_subtree_sum, right_count = getAverageOfSubtree(node.right)\n",
    "            subtree_sum = node.val + left_subtree_sum + right_subtree_sum\n",
    "            subtree_count = left_count + right_count + 1\n",
    "            if node.val == subtree_sum // subtree_count:\n",
    "                self.res += 1\n",
    "            return subtree_sum, subtree_count\n",
    "        getAverageOfSubtree(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root):\n",
    "            nonlocal ans\n",
    "            if not root:\n",
    "                return 0,0\n",
    "            l = dfs(root.left)\n",
    "            r = dfs(root.right)\n",
    "            value = l[0] + r[0] + root.val\n",
    "            count = l[1] + r[1] + 1\n",
    "            if root.val == value//count:\n",
    "                ans += 1\n",
    "            return value,count\n",
    "        \n",
    "        ans = 0\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "def postprev(node):\n",
    "    if node is None:\n",
    "        return 0, 0, 0\n",
    "    lnum, lsum, lres = postprev(node.left)\n",
    "    rnum, rsum, rres = postprev(node.right)\n",
    "    nums = lnum + rnum + 1\n",
    "    sums = lsum + rsum + node.val\n",
    "    res = lres + rres\n",
    "    if sums // nums == node.val:\n",
    "        res += 1\n",
    "    return nums, sums, res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        _, _, res = postprev(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "\n",
    "        def traverse(root):\n",
    "            if root is None:\n",
    "                return 0, 0\n",
    "            nonlocal res\n",
    "\n",
    "            leftsum, leftcount = traverse(root.left)\n",
    "            rightsum, rightcount = traverse(root.right)\n",
    "\n",
    "            if (leftsum + rightsum + root.val) // (rightcount + leftcount + 1) == root.val:\n",
    "                res += 1\n",
    "            \n",
    "            return leftsum + rightsum + root.val, rightcount + leftcount + 1\n",
    "\n",
    "        traverse(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "            leftSum, leftCnt = dfs(node.left)\n",
    "            rightSum, rightCnt = dfs(node.right)\n",
    "            subSum = leftSum + rightSum + node.val\n",
    "            subCnt = leftCnt + rightCnt + 1\n",
    "            if node.val == subSum // subCnt:\n",
    "                nonlocal res\n",
    "                res += 1\n",
    "            return subSum, subCnt\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "def postprev(node):\n",
    "    lnum, lsum, lres = (0, 0, 0) if node.left is None else postprev(node.left) \n",
    "    rnum, rsum, rres = (0, 0, 0) if node.right is None else postprev(node.right)\n",
    "    nums = lnum + rnum + 1\n",
    "    sums = lsum + rsum + node.val\n",
    "    res = lres + rres\n",
    "    if sums // nums == node.val:\n",
    "        res += 1\n",
    "    return nums, sums, res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        _, _, res = postprev(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.out = 0\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0,0\n",
    "            # 叶子节点\n",
    "            elif not (root.left or root.right):\n",
    "                self.out += 1\n",
    "                return root.val,1\n",
    "            else:\n",
    "                left_sum,left_num = dfs(root.left)\n",
    "                right_sum,right_num = dfs(root.right)\n",
    "\n",
    "                cur_sum = root.val + left_sum+right_sum\n",
    "                cur_num = 1 + left_num+right_num\n",
    "\n",
    "                if cur_sum//cur_num == root.val:\n",
    "                    self.out += 1\n",
    "                return cur_sum,cur_num\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if not root:\n",
    "                return 0, 0\n",
    "            ls, ln = dfs(root.left)\n",
    "            rs, rn = dfs(root.right)\n",
    "            ns = ls + rs + root.val * 2\n",
    "            nn = ln + rn + 2\n",
    "            if ns // nn == root.val:\n",
    "                # print(f'{nn}:{ns / nn}')\n",
    "                res += 1\n",
    "            return ns, nn\n",
    "\n",
    "        dfs(root)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root: Optional[TreeNode]) -> List[int]:\n",
    "            a = [root.val, 1, 0]\n",
    "            if root.left == None and root.right == None:\n",
    "                a[2] = 1\n",
    "                return a\n",
    "            if root.left != None:\n",
    "                t = dfs(root.left)\n",
    "                a[0] += t[0]\n",
    "                a[1] += t[1]\n",
    "                a[2] += t[2]\n",
    "            if root.right != None:\n",
    "                t = dfs(root.right)\n",
    "                a[0] += t[0]\n",
    "                a[1] += t[1]\n",
    "                a[2] += t[2]\n",
    "            if a[0] // a[1] == root.val:\n",
    "                a[2] += 1\n",
    "            return a\n",
    "        return dfs(root)[2]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        cnt = 0\n",
    "        res = 0\n",
    "        def dfs(node):\n",
    "            if node == None:\n",
    "                return 0\n",
    "            nonlocal cnt, res\n",
    "            cur = cnt\n",
    "            cnt += 1\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            sum = node.val + left + right\n",
    "            if sum // (cnt - cur) == node.val:\n",
    "                res += 1\n",
    "            return sum\n",
    "        dfs(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "def postprev(node):\n",
    "    lnum, lsum, lres = (0, 0, 0) if node.left is None else postprev(node.left) \n",
    "    rnum, rsum, rres = (0, 0, 0) if node.right is None else postprev(node.right)\n",
    "    nums = lnum + rnum + 1\n",
    "    sums = lsum + rsum + node.val\n",
    "    res = lres + rres + (sums // nums == node.val)\n",
    "    return nums, sums, res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        _, _, res = postprev(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def sumOfSubtree(node: Optional[TreeNode]):\n",
    "            if not node:\n",
    "                return 0, 0, 0\n",
    "            if not node.left and not node.right:\n",
    "                return 1, node.val, 1\n",
    "            leftC, leftS, leftA = sumOfSubtree(node.left)\n",
    "            rightC, rightS, rightA = sumOfSubtree(node.right)\n",
    "            c = leftC + rightC + 1\n",
    "            s = leftS + rightS + node.val\n",
    "            ans = leftA + rightA\n",
    "            if s // c == node.val:\n",
    "                ans += 1\n",
    "            return c, s, ans\n",
    "            \n",
    "        return sumOfSubtree(root)[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def scan(n, p):\n",
    "            if not n:\n",
    "                return\n",
    "            p.append(n)\n",
    "            scan(n.left, p)\n",
    "            scan(n.right, p)\n",
    "        ns = []\n",
    "        scan(root, ns)\n",
    "        \n",
    "        ans = 0\n",
    "        for n in ns:\n",
    "            tmp=[]\n",
    "            scan(n, tmp)\n",
    "            if n.val == sum([i.val for i in tmp])//len(tmp):\n",
    "                ans +=1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        def dfs(node: TreeNode):\n",
    "            nonlocal res\n",
    "            if not node:\n",
    "                return [0,0]\n",
    "            left_sum,left_count= dfs(node.left)\n",
    "            right_sum,right_count= dfs(node.right)\n",
    "            s = node.val+left_sum+right_sum\n",
    "            count = 1+left_count+right_count\n",
    "            if s//count == node.val:\n",
    "                res += 1\n",
    "            return [s,count]\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        # if not root:\n",
    "        #     return 0\n",
    "        # if not root.right and not root.left:\n",
    "        #     return 1\n",
    "        # def pre_order(root):\n",
    "        #     ans=[]\n",
    "        #     if not root:\n",
    "        #         return 0,0\n",
    "        #     ans=root.val\n",
    "        #     return ans+pre_order(root.left)[0]+pre_order(root.right)[0],1+pre_order(root.left)[1]+pre_order(root.right)[1]\n",
    "        # if pre_order(root)[0]//pre_order(root)[1]==root.val:\n",
    "        #     return 1+self.averageOfSubtree(root.left)+self.averageOfSubtree(root.right)\n",
    "        # return self.averageOfSubtree(root.left)+self.averageOfSubtree(root.right)\n",
    "        ans = 0\n",
    "        def sumtree(node):\n",
    "            nonlocal ans\n",
    "            if node is None:\n",
    "                return 0, 0\n",
    "            total, cnt = tuple(map(sum, zip(sumtree(node.left), sumtree(node.right), (node.val, 1))))\n",
    "            ans += total // cnt == node.val\n",
    "            return total, cnt\n",
    "        sumtree(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return [0, 0] # sum, count\n",
    "            # if not root.left and not root.right:\n",
    "            #     self.res += 1\n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "            total = left[0] + right[0] + root.val\n",
    "            count = left[1] + right[1] + 1\n",
    "            if total//count == root.val:\n",
    "                self.res += 1\n",
    "            return [total + root.val, count +1]\n",
    "\n",
    "        self.res = 0\n",
    "        dfs(root)\n",
    "        return self.res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def _DFS(root):\n",
    "            nonlocal ans\n",
    "            leftCnt, leftSum = 0, 0\n",
    "            if root.left:\n",
    "                leftCnt, leftSum = _DFS(root.left)\n",
    "            rightCnt, rightSum = 0, 0\n",
    "            if root.right:\n",
    "                rightCnt, rightSum = _DFS(root.right)\n",
    "            \n",
    "            curSum = root.val + leftSum + rightSum\n",
    "            curCnt = 1 + leftCnt + rightCnt\n",
    "            if root.val == curSum//curCnt :\n",
    "                ans += 1\n",
    "            return curCnt, curSum\n",
    "        \n",
    "        _DFS(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        # 相当于先序遍历了 \n",
    "        def dfs(root: Optional[TreeNode]):\n",
    "            nonlocal ans \n",
    "            if not root:\n",
    "                return 0, 0\n",
    "            \n",
    "            l = dfs(root.left)\n",
    "            r = dfs(root.right)\n",
    "            # value左右子树之和，count左右子树节点总和\n",
    "            value = l[0] + r[0] + root.val\n",
    "            count = l[1] + r[1] + 1\n",
    "            if root.val == value // count:\n",
    "                ans += 1\n",
    "            return value, count    \n",
    "        \n",
    "        # 主函数\n",
    "        ans = 0\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        \n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0,0\n",
    "            \n",
    "            ls,lc = dfs(node.left)\n",
    "            rs,rc = dfs(node.right)\n",
    "            c = 1+lc+rc\n",
    "            s = node.val+ls+rs\n",
    "            nonlocal res\n",
    "            res += node.val==s//c\n",
    "            return s,c\n",
    "\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = []\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "            left, left_n = dfs(node.left)\n",
    "            right, right_n = dfs(node.right)\n",
    "            s = left+right+node.val\n",
    "            n = left_n + right_n + 1\n",
    "            if s//n == node.val:\n",
    "                res.append(1)\n",
    "            return s, n\n",
    "        \n",
    "        dfs(root)\n",
    "        return sum(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(cur):\n",
    "            if not cur:\n",
    "                return 0, 0\n",
    "\n",
    "            c = 1\n",
    "            s = cur.val\n",
    "\n",
    "            a, b = dfs(cur.left)\n",
    "            c += a\n",
    "            s += b\n",
    "\n",
    "            a, b = dfs(cur.right)\n",
    "            c += a\n",
    "            s += b\n",
    "\n",
    "            if s // c == cur.val:\n",
    "                nonlocal ans\n",
    "                ans += 1\n",
    "            return c, s\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.count = 0\n",
    "\n",
    "        def helper(root):\n",
    "            if not root:\n",
    "                return 0, 0\n",
    "            leftTotal, leftCount = helper(root.left)\n",
    "            rightTotal, rightCount = helper(root.right)\n",
    "            total = leftTotal + rightTotal + root.val\n",
    "            totalCount = leftCount + rightCount + 1\n",
    "            if root.val == total // totalCount:\n",
    "                self.count += 1\n",
    "            return total, totalCount\n",
    "        \n",
    "        helper(root)\n",
    "        return self.count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node):  # cnt, sum\n",
    "            nonlocal res\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "            cnt_l, sum_l = dfs(node.left)\n",
    "            cnt_r, sum_r = dfs(node.right)\n",
    "            cnt, sum = cnt_l + cnt_r + 1, sum_l + sum_r + node.val\n",
    "            if sum // cnt == node.val:\n",
    "                res += 1\n",
    "            return cnt, sum\n",
    "\n",
    "        res = 0\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    result=0\n",
    "    def dfs(self,root):\n",
    "        if root == None:\n",
    "            return 0,0\n",
    "        if root.left ==None and root.right ==None:\n",
    "            self.result += 1\n",
    "            return root.val,1\n",
    "        left_sum,left_count = self.dfs(root.left)\n",
    "        right_sum,right_count = self.dfs(root.right)\n",
    "        root_total = root.val+left_sum+right_sum\n",
    "        root_count = 1+left_count+right_count\n",
    "        print(f\"root:{root.val}\")\n",
    "        print(f\"left_sum:{left_sum}---right_sum:{right_sum}\")\n",
    "        print(f\"total{root_total}--left_count:{left_count}_right_count{right_count}\")\n",
    "        if root.val ==int(root_total/root_count):\n",
    "            self.result +=1\n",
    "        return root_total,1+left_count+right_count\n",
    "        \n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.dfs(root)\n",
    "        return self.result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans=0\n",
    "        def f(r):\n",
    "            nonlocal ans\n",
    "            c=1\n",
    "            s=r.val\n",
    "            if r:\n",
    "                if r.left:\n",
    "                    c0,s0=f(r.left)\n",
    "                    c+=c0\n",
    "                    s+=s0 \n",
    "                if r.right:\n",
    "                    c0,s0=f(r.right)\n",
    "                    c+=c0 \n",
    "                    s+=s0 \n",
    "                if s//c==r.val:\n",
    "                    ans+=1\n",
    "                return c,s\n",
    "        f(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "\n",
    "        def traverse(root):\n",
    "            if root is None:\n",
    "                return 0, 0\n",
    "            nonlocal res\n",
    "\n",
    "            leftsum, leftcount = traverse(root.left)\n",
    "            rightsum, rightcount = traverse(root.right)\n",
    "\n",
    "            if (leftsum + rightsum + root.val) // (rightcount + leftcount + 1) == root.val:\n",
    "                res += 1\n",
    "            \n",
    "            return leftsum + rightsum + root.val, rightcount + leftcount + 1\n",
    "\n",
    "        traverse(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        ans = 0\n",
    "        \n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return [0, 0]\n",
    "            res = [node.val, 1]\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            res[0] += left[0]+right[0]\n",
    "            res[1] += left[1] + right[1]\n",
    "            if res[0]//res[1] == node.val:\n",
    "                ans += 1\n",
    "            return res\n",
    "        \n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "    \n",
    "    def dfs(self, node):\n",
    "        if node == None:\n",
    "            return 0, 0\n",
    "        n_node = 1\n",
    "        curr_sum = node.val\n",
    "        if node.left:\n",
    "            left_n, left_sum = self.dfs(node.left)\n",
    "            n_node += left_n\n",
    "            curr_sum += left_sum\n",
    "        if node.right:\n",
    "            right_n, right_sum = self.dfs(node.right)\n",
    "            n_node += right_n\n",
    "            curr_sum += right_sum\n",
    "        if curr_sum // n_node == node.val:\n",
    "            self.res += 1\n",
    "        return n_node, curr_sum\n",
    "\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "            \n",
    "            left_sum, left_cnt = dfs(node.left)\n",
    "            right_sum, right_cnt = dfs(node.right)\n",
    "\n",
    "            this_sum = left_sum + right_sum + node.val\n",
    "            this_cnt = left_cnt + right_cnt + 1\n",
    "            avg = this_sum // this_cnt\n",
    "            if avg==node.val:\n",
    "                ans += 1\n",
    "            return this_sum, this_cnt\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        res=0\n",
    "        def dfs(root:Optional[TreeNode]):\n",
    "            nonlocal res\n",
    "            if not root:\n",
    "                return 0, 0\n",
    "            leftsum, leftcnt=dfs(root.left)\n",
    "            rightsum, rightcnt=dfs(root.right)\n",
    "            s=leftsum+rightsum+root.val\n",
    "            c=leftcnt+rightcnt+1\n",
    "            if s//c==root.val:\n",
    "                res+=1\n",
    "            return s, c\n",
    "        \n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(root):\n",
    "            nonlocal ans\n",
    "            if not root: return 0, 0\n",
    "            l, cnt_l = dfs(root.left)\n",
    "            r, cnt_r = dfs(root.right)\n",
    "            s = l + r + root.val\n",
    "            cnt = cnt_l + cnt_r + 1\n",
    "            if int(s / cnt) == root.val:\n",
    "                ans += 1\n",
    "            return s, cnt\n",
    "        \n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        su=0\n",
    "        cnt=0\n",
    "        self.res=0\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return 0,0\n",
    "            \n",
    "            ls,lc=dfs(root.left)\n",
    "            rs,rc=dfs(root.right)\n",
    "            s=ls+rs+root.val\n",
    "            c=lc+rc+1\n",
    "            if s//c==root.val:\n",
    "                self.res+=1\n",
    "            return s,c\n",
    "        dfs(root)\n",
    "        return self.res\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        \"\"\"\n",
    "        post order traversal, return summation and # of nodes\n",
    "        result pushed to global variable\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "\n",
    "        def dfs(node: Optional[TreeNode]) -> tuple[int, int]:\n",
    "            if node is None:    return (0, 0)\n",
    "\n",
    "            nonlocal res\n",
    "\n",
    "            left_res = dfs(node.left)\n",
    "            right_res = dfs(node.right)\n",
    "\n",
    "            summation = left_res[0] + right_res[0] + node.val\n",
    "            count = left_res[1] + right_res[1] + 1\n",
    "            if summation // count == node.val:\n",
    "                res += 1\n",
    "\n",
    "            return (summation, count)\n",
    "        \n",
    "        dfs(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        cnt = 0\n",
    "        def dfs(root):\n",
    "            nonlocal cnt\n",
    "            if not root:\n",
    "                return (0, 0)\n",
    "            #print(root)\n",
    "            left_v, cnt_l = dfs(root.left)\n",
    "            print(cnt_l)\n",
    "            right_v, cnt_r = dfs(root.right)\n",
    "            if root.val == (left_v + right_v +root.val)//(cnt_l+cnt_r+1):\n",
    "                cnt += 1\n",
    "            v = left_v + right_v + root.val\n",
    "            w = cnt_l + cnt_r +1\n",
    "            return v, w\n",
    "        dfs(root)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        ans=0\n",
    "        def dfs(root):\n",
    "            nonlocal ans\n",
    "            if root is None:\n",
    "                return 0,0\n",
    "            left_sum,left_node=dfs(root.left)\n",
    "            right_sum,right_node=dfs(root.right)\n",
    "            if (right_sum+left_sum+root.val)//(left_node+right_node+1)==root.val:\n",
    "                ans+=1\n",
    "            return root.val+left_sum+right_sum,left_node+right_node+1\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:\n",
    "        cnt,summ = 0,0\n",
    "        ret = 0\n",
    "        def dfs(node):\n",
    "            nonlocal ret\n",
    "            summ,cnt = node.val,1\n",
    "            if node.left:\n",
    "                s,c = dfs(node.left)\n",
    "                summ += s\n",
    "                cnt += c\n",
    "            if node.right:\n",
    "                s,c = dfs(node.right)\n",
    "                summ += s\n",
    "                cnt += c\n",
    "            if node.val == summ//cnt:\n",
    "                print(node.val,summ,cnt)\n",
    "                ret +=1\n",
    "            return summ,cnt\n",
    "        dfs(root)\n",
    "        return ret\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
